#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        int ans = 1;
        vector<int> inDegrees(n + 1);
        vector<int> outDegrees(n + 1);
        for (auto& v : trust)
        {
            ++inDegrees[v[1]];
            ++outDegrees[v[0]];
        }
        for (int i = 1; i <= n; ++i)
            if (inDegrees[i] == n - 1 && outDegrees[i] == 0)
                return i;
        return -1;
    }

    string countAndSay(int n) {
        string res = "1";
        for (int i = 1; i < n; ++i)
        {
            string tmp;
            int len = res.size();
            for (int left = 0, right = 0; right < len;)
            {
                while (right < len && res[right] == res[left]) ++right;
                tmp += to_string(right - left) + res[left];
                left = right;
            }
            res = tmp;
        }
        return res;
    }

    bool reportSpam(vector<string>& message, vector<string>& bannedWords) {
        unordered_map<string, int> mp;
        set<string> vs(bannedWords.begin(), bannedWords.end());
        for (auto& s : message)
            mp[s] += 1;
        int cnt = 0;
        for (auto& s : vs)
        {
            if (mp.count(s)) cnt += mp[s];
            if (cnt >= 2) return true;
        }
        return false;
    }

    long long validSubstringCount(string s, string t) {
        if (s.length() < t.length()) return 0;

        int cnt[26]{};
        for (char ch : t)
            ++cnt[ch - 'a'];
        int less = 0;
        for (int n : cnt)
            less += n > 0;

        long long ans = 0, left = 0;

        for (char c : s)
        {
            less -= --cnt[c - 'a'] == 0;
            while (less == 0)
            {
                less += cnt[s[left++] - 'a']++ == 0;
            }
            ans += left;
        }
        return ans;
    }

    class Node {
    public:
        int val;
        Node* next;
        Node* random;

        Node(int _val) {
            val = _val;
            next = NULL;
            random = NULL;
        }
    };

    Node* copyRandomList(Node* head) {
        if (head == nullptr) return nullptr;
        Node* cur = head;
        while (cur)
        {
            Node* newNode = new Node(cur->val);
            newNode->next = cur->next;
            cur->next = newNode;
            cur = newNode->next;
        }
        cur = head;
        while (cur)
        {
            if (cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        cur = head->next;
        Node* pre = head, * res = head->next;
        while (cur->next)
        {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr;
        return res;
    }

    Node* _copyRandomList(Node* head) {
        map<Node*, Node*> mp;
        Node* copyhead = nullptr, * copytail = nullptr;
        Node* cur = head;
        while (cur)
        {
            if (!copyhead)
                copyhead = copytail = new Node(cur->val);
            else
            {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            mp[cur] = copytail;
            cur = cur->next;
        }
        cur = head;
        Node* copy = copyhead;
        while (cur)
        {
            if (!cur->random)
                copy->random = nullptr;
            else
                copy->random = mp[cur->random];
            copy = copy->next;
            cur = cur->next;
        }
        return copyhead;
    }

    struct KVcom
    {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y)
        {
            return x.second > y.second || (x.second == y.second && x.first < y.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> mp;
        for (auto w : words)
        {
            ++mp[w];
        }
        vector<pair<string, int>> v(mp.begin(), mp.end());
        sort(v.begin(), v.end(), KVcom());
        vector<string> ans;
        for (int i = 0; i < k; ++i)
        {
            ans.push_back(v[i].first);
            v.pop_back();
        }
        return ans;
    }

    struct KVcom
    {
        bool operator()(const pair<string, int>& x, const pair<string, int>& y)
        {
            return x.second < y.second || (x.second == y.second && x.first > y.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> mp;
        for (auto& w : words)
            ++mp[w];
        priority_queue<pair<string, int>, vector<pair<string, int>>, KVcom> hp(mp.begin(), mp.end());
        vector<string> ans;
        for (int i = 0; i < k; ++i)
        {
            ans.push_back(hp.top().first);
            hp.pop();
        }
        return ans;
    }
};